package org.czl.leetCode1;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class L3186 {
    public long maximumTotalDamage(int[] power) {
        Map<Integer, Integer> map = new HashMap<>();
        for(int x : power)map.merge(x, 1, Integer::sum);//x为分数, map中value表示该分数出现次数
        int k = 0;
        int n = map.size();
        int[] a = new int[n];
        for(int x : map.keySet()){
            a[k++] = x;
        }
        Arrays.sort(a);
        long[] dp = new long[n + 2];
        int j = 0;
        for(int i = 0; i < n; i++){
            int x = a[i];
            while(a[j] < x - 2){
                j++;
            }
            dp[i + 1] = Math.max(dp[i], dp[j] + (long)map.get(x) * x);
        }
        return dp[n];
    }
}
